def insertion_sort_recursive(A,i):
    if i==0:
        return A
    else:
        insertion_sort_recursive(A,i-1)
        key=A[i]
        j=i-1
        while j>=0 and A[j]>key:
            A[j+1]=A[j]
            j-=1
        A[j+1]=key
        return A

def do_insertion_sort(A):
    n=len(A)
    return insertion_sort_recursive(A,n-1)

if __name__=='__main__':
    A=[11,5,2,6,77,23,8,4,123]
    print 'A=', A
    print 'result=', do_insertion_sort(A)
            
